Từ lặp lại đến đệ quy: Tái cấu trúc tư duy

Đệ quy (Recursion) là một phương pháp thay đổi sâu sắc cách tiếp cận giải quyết vấn đề. Khi xử lý các bài toán như cộng dồn danh sách,...phương pháp lặp lại(Bảng mã 4-2) phụ thuộc vào bộ đếm tích lũy rõ ràng theSum và kiểm soát trạng thái vòng lặp; trong khi phương pháp đệ quy dựa vào định nghĩa toán học sâu sắc:

Đệ quy không chỉ đơn giản là hàm gọi chính nó, mà còn phân tách vấn đề phức tạp thành các vấn đề con nhỏ hơn có cấu trúc giống nhau, cốt lõi nằm ở việc nhận diện sự tương tự giữa vấn đề lớn và vấn đề contính tự tương đồng. Quá trình đệ quy bao gồm hai giai đoạn đối xứng:

• Giai đoạn "đi xuống": liên tục cắt danh sách và đẩy vào ngăn xếp gọi, cho đến khi đạt được trường hợp cơ sở có thể giải quyết đượctrường hợp cơ sở(Base Case).
• Giai đoạn "quay về": bắt đầu từ trạng thái đơn giản nhất, lần lượt quay ngược lên từng tầng và gộp kết quả.